package main.leetcode.primary.from301to400;

/**
 * 343.整数拆分
 *
 * <p>给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * <p>示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
 *
 * <p>示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 *
 * <p>说明: 你可以假设 n 不小于 2 且不大于 58。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/integer-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex343 {
    public static void main(String[] args) {
        System.out.println(new ex343().integerBreak(5));
    }
    // 记忆化技术/备忘录法——自顶向下
    //    public int integerBreak(int n) {
    //        if (n == 2) return 1;
    //        if (n == 3) return 2;
    //        // 存储整数i的最大化乘积
    //        int[] mem = new int[n + 1];
    //        mem[0] = 0;
    //        mem[1] = 1;
    //        mem[2] = 1;
    //        mem[3] = 2;
    //        for (int i = 4; i <= n; ++i) {
    //            mem[i] = memoization(mem, i);
    //        }
    //        return mem[n];
    //    }
    //
    //    private int memoization(int[] mem, int n) {
    //        if (mem[n] > 0) {
    //            return mem[n];
    //        }
    //        int res = 0;
    //        for (int i = 1; i < n; ++i) {
    //            // 要同时与仅分成两段的情况进行对比
    //            res = Math.max(res, Math.max(i * (n - i), i * memoization(mem, n - i)));
    //        }
    //        return res;
    //    }

    // dp——自底向上
    //    public int integerBreak(int n) {
    //        if (n == 2) return 1;
    //        if (n == 3) return 2;
    //        // 存储整数i的最大化乘积
    //        int[] dp = new int[n + 1];
    //        dp[2] = 1;
    //        for (int i = 3; i <= n; ++i) {
    //            for (int j = 1; j < i; ++j) {
    //                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
    //            }
    //        }
    //        return dp[n];
    //    }

    // 数学推理
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
}
